package hungle.oregonstate.edu.datastructure;

import java.util.Random;

// TODO: implement delete node BSTree
/**
 * The Class BSTree.
 *
 * @param <K> the key type
 * @param <V> the value type
 */
public class BSTree<K extends Comparable<K>, V >{
	
	/** The root. */
	private BinaryTreeNode<K, V> root = null;
	
	/** The tree size. */
	private int treeSize;
	
	/**
	 * Instantiates a new Binary Search Tree.
	 */
	public BSTree(){
		root = null;
		treeSize = 0;
	}
	
	/**
	 * Search a key in the BSTree
	 *
	 * @param key 
	 * @return the binary tree node contains the key
	 */
	public BinaryTreeNode<K, V> search(K key){
		return search(root, key);
	}
	
	/**
	 * Search the node contains key of the tree
	 * rooted at ptr
	 *
	 * @param ptr the root of the tree
	 * @param key the key
	 * @return the binary tree node
	 */
	private BinaryTreeNode<K, V> search(BinaryTreeNode<K, V> ptr, K key){
		if (ptr.getKey().compareTo(key) == 0) return ptr;
		else if (ptr.getKey().compareTo(key) > 0){
			if (ptr.hasLeftChild()) return search(ptr.getLeftChild(), key);
			else return null;
		} else {
			if (ptr.hasRightChild()) return search(ptr.getRightChild(), key);
			else return null;
		}
	}
	
	/**
	 * Insert a node to the BStree
	 *
	 * @param node the node
	 */
	public void insert(BinaryTreeNode<K, V> node){
		if (root == null) {
			root = node;
		}  else {
			insert(root, node);
		}
		
	}
	
	/**
	 * Insert a node to the BStree rooted at ptr
	 *
	 * @param ptr the root of the tree
	 * @param node the inserted node
	 */
	private void insert(BinaryTreeNode<K, V> ptr, BinaryTreeNode<K, V> node){
		if (ptr.getKey().compareTo(node.getKey()) > 0){ 
			/* key of the inserted node is smaller than key of ptr
			 */
			if (ptr.hasLeftChild()){
				insert(ptr.getLeftChild(), node);
			} else {
				ptr.insertLeft(node);
				node.updateParent(ptr);
			}
		} else {
			/*
			 * key of the inserted node is larger than or equal key of ptr
			 */
			if(ptr.hasRightChild()){
				insert(ptr.getRightChild(), node);
			} else {
				ptr.insertRight(node);
				node.updateParent(ptr);
			}
		}
	}
	
	/**
	 * Delete.
	 *
	 * @param key the key
	 * @return true, if successful
	 */
	public boolean delete(BinaryTreeNode<K, V> node) {
		if (!node.hasLeftChild() && !node.hasRightChild()){
			// node if a leaf
			return replaceNode(node, null);
		} else if(!node.hasLeftChild()) {
			// if the node does not have a left child
			BinaryTreeNode<K, V> parent = node.getParent();
			if (parent == null){
				// if the node to be deleted is a root
				node.getRightChild().updateParent(null);
				root = node.getRightChild();
				return true;
			} else {
				if (parent.hasRightChild()
						&& parent.getRightChild().getKey()
								.compareTo(node.getKey()) == 0) {
					parent.updateRight(node.getRightChild());
				} else {
					parent.updateLeft(node.getRightChild());
				}
				node.getRightChild().updateParent(parent);
			}
			return true;
		} else if (!node.hasRightChild()){
			BinaryTreeNode<K, V> parent = node.getParent();
			if (parent == null){
				node.getLeftChild().updateParent(null);
				root = node.getLeftChild();
			} else {
				if (parent.hasRightChild()
						&& parent.getRightChild().getKey()
								.compareTo(node.getKey()) == 0) {
					parent.updateRight(node.getLeftChild());
				} else {
					parent.updateLeft(node.getLeftChild());
				}
				node.getLeftChild().updateParent(parent);
			}
			
		} else {
			// if the node to be deleted has both left and right child
			// Find the left most node of the right branch
			// Replace the node by the left most of the right branch
			// Delete the left most node of the right
			BinaryTreeNode<K, V> leftMostOfRight = findLeftMost(node.getRightChild());
			delete(leftMostOfRight);
			return replaceNode(node, leftMostOfRight);
		}
		return true;
	}
	/**
	 * Delete a node identified by key
	 *
	 * @param key the key of the node to be deleted
	 * @return true, if successful
	 */
	
	public boolean delete(K key){
		BinaryTreeNode<K, V> node = search(key);
		if (node == null) return false;
		else {
			delete(node);
			return true;
		}
	}
	
	
	/**
	 * Replace the node pointed by ptr and node
	 * Replacement of ptr by a null is allowed
	 *
	 * @param ptr the node to be replaced
	 * @param node the replacing node
	 * @return true of ptr is not the root of the tree
	 */
	
	private boolean replaceNode(BinaryTreeNode<K, V> ptr, BinaryTreeNode<K, V> node){
		BinaryTreeNode<K, V> parent = ptr.getParent();
		if (parent != null) {
			// if the node to be replaced is not the root of the tree
			if (parent.hasRightChild()
					&& parent.getRightChild().getKey().compareTo(ptr.getKey()) == 0) {
				parent.updateRight(node);
			} else {
				parent.updateLeft(node);
			}
			
		}  else {
			root = node;
		}
		if (node != null){
			node.updateRight(ptr.getRightChild());
			if(ptr.hasRightChild()) ptr.getRightChild().updateParent(node);
			node.updateLeft(ptr.getLeftChild());
			if(ptr.hasLeftChild()) ptr.getLeftChild().updateParent(node);
			node.updateParent(parent);
		}
		return true;
	}
	
	
	/**
	 * Find the right most node of the tree rooted at ptr
	 *
	 * @param ptr the root of the tree
	 * @return the right most node
	 */
	public BinaryTreeNode<K, V> findRightMost(BinaryTreeNode<K, V> ptr){
		if (ptr.hasRightChild())
			return findRightMost(ptr.getRightChild());
		else return ptr;
	}
	/**
	 * Find the left most node of the tree rooted at ptr
	 *
	 * @param ptr the root of the tree
	 * @return the left most node
	 */
	public BinaryTreeNode<K, V> findLeftMost(BinaryTreeNode<K, V> ptr){
		if (ptr.hasLeftChild()){
			return findLeftMost(ptr.getLeftChild());
		} else return ptr;
	}
	
	
	
	
	/**
	 * Gets the tree size.
	 *
	 * @return the tree size
	 */
	public int getTreeSize(){
		return treeSize;
	}
	
	/**
	 * Gets the root.
	 *
	 * @return the root
	 */
	public BinaryTreeNode<K, V> getRoot(){
		return root;
	}
	
	/**
	 * Sets the root.
	 *
	 * @param root the root
	 */
	public void setRoot(BinaryTreeNode<K, V> root){
		this.root = root;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	public String toString(){
		return toString(root);
	}
	
	/**
	 * To string.
	 *
	 * @param node the node
	 * @return the string
	 */
	private String toString(BinaryTreeNode<K, V> node){
		StringBuilder sbd = new StringBuilder();
		sbd.append(node.getKey());
		if (node.getParent() != null) sbd.append(":" + node.getParent().getKey());
		else sbd.append(":");
		String leftStr = "";
		String rightStr = "";
		if (node.hasLeftChild()){
			sbd.append( ":" + node.getLeftChild().getKey());
			leftStr = "\n" + toString(node.getLeftChild());
		} else {
			sbd.append(":");
		}
		if (node.hasRightChild()){
			sbd.append(":" + node.getRightChild().getKey());
			rightStr =  "\n" + toString(node.getRightChild());
		} else {
			sbd.append(":");
		}
		sbd.append(leftStr);
		sbd.append(rightStr);
		return sbd.toString() ;
	}
	/**
	 * Balanced insertion.
	 *
	 * @param treePtr the tree ptr
	 * @param node the node
	 */
//	private void balancedInsertion(BinaryTreeNode<K,V> treePtr, BinaryTreeNode<K, V> node){
//		if (!treePtr.hasLeftChild()){
//			treePtr.insertLeft(node);
//			treePtr.getValue().increaseLeftSize(1);
//		}
//		else if(!treePtr.hasRightChild()){
//			treePtr.insertRight(node);
//			//treePtr.getValue().increaseRightSize(1);
//		}
//		else if (treePtr.getLeftSize() > treePtr.getRightSize()){
//		    treePtr.getValue().increaseRightSize(1);
//			treePtr = treePtr.getRightChild();
//			balancedInsertion(treePtr, node);
//			
//		} else {
//			treePtr.getValue().increaseLeftSize(1);
//			treePtr = treePtr.getLeftChild();
//			balancedInsertion(treePtr, node);
//		}
//		
//	}
//	
//	/**
//	 * Balanced insertion.
//	 *
//	 * @param node the node
//	 */
//	public void balancedInsertion(BinaryTreeNode<K, V> node){
//		balancedInsertion(root, node);
//		treeSize ++;
//	}
	
	
}


